#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

/*
输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的
最大值。要求时间复杂度为O(n)。例如输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10,-4,7,2}，因此输
出为该子数组的和18
*/

int main()
{
	int arr[8] = { 1,-2,3,10,-4,7,2,-5 };
	int i = 0;
	int sum = 0;//定义当前坐标下元素累加的和
	int max = 0;//定义当前子数列累加最大值
	for (i = 0; i < 8; i++)
	{
		if (sum + arr[i] < 0)
			sum = 0;/*如果上一次累加和加上当前元素结果为负值，那么它即使
			加上别的数也只会使其缩小，所以sum=0干脆扔掉这个拖油瓶，
			并且使累加从下一个元素重新开始*/
		else
			sum += arr[i];/*如果不为0，那么sum存储当前和并且累加，如果
			if语句执行，这条代码会跳过当前这个使sum变为负数的元素*/
		if (sum > max)
			max = sum;//判断sum与max的大小
	}
	printf("%d", max);
	return 0;
}
